POI2008 Building blocks

POI
BIT, 线段树

POI2008 Building blocks

题目大意：

有n块砖，我们现在希望有连续的k块砖的高度一样。你可以选择以下两种动作：

  1. 把某一块砖高度减一。
  2. 把某一块砖高度加一。

求完成任务最少要操作几次。

（ $n \le 10^5$ , $h \le 10^6$ ）

题解：

首先肯定是枚举所有长度为k的区间。

接下来问题就变成了，已知一个区间，问把区间中所有数字权值都变相同，需要的最小代价。

有一个很明显的贪心：把所有的数字都变成，在这些数中排名为$(k+1)/2$的那个数。

于是问题就分成了两步：

  1. 找到排名为$(k+1)/2$的那个数$x$。
  2. 统计比$x$大的数的权值和$sum1$和个数$cnt1$，以及小于等于$x$的权值和$sum2$和个数$cnt2$。

那么答案即为：$sum1-cnt1 \times x + cnt2 \times x -sum2$.

我们可以利用一个线段树在$O(logh)$的时间内找到$x$，并用一个$BIT$来求权值和。

由于内存只有32MB，直接权值线段树会被卡。因而我们离散一下，复杂度变为$O(nlogn)$.

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=100005;
int n,k,num[N],pos,tmp[N],len;
struct Segment_Tree{
	struct node{
		int L,R,cnt;
	}tree[N<<2];
	void build(int L,int R,int p){
		tree[p].L=L,tree[p].R=R,tree[p].cnt=0;
		if(L==R)return;
		int mid=L+R>>1;
		build(L,mid,p<<1);
		build(mid+1,R,p<<1|1);
	}
	void up(int p){
		tree[p].cnt=tree[p<<1].cnt+tree[p<<1|1].cnt;
	}
	void update(int x,int v,int p){
		if(tree[p].L==tree[p].R){
			tree[p].cnt+=v;
			return;
		}
		int mid=tree[p].L+tree[p].R>>1;
		if(x<=mid)update(x,v,p<<1);
		else update(x,v,p<<1|1);
		up(p);
	}
	int sum(int L,int R,int p){
		if(L>R)return 0;
		if(tree[p].L==L&&tree[p].R==R){
			return tree[p].cnt;
		}
		int mid=tree[p].L+tree[p].R>>1;
		if(R<=mid)return sum(L,R,p<<1);
		else if(L>mid)return sum(L,R,p<<1|1);
		else return sum(L,mid,p<<1)+sum(mid+1,R,p<<1|1);
	}
	int query(int k,int p){
		if(tree[p].L==tree[p].R)return tree[p].L;
		int cntL=tree[p<<1].cnt;
		if(cntL>=k)return query(k,p<<1);
		else return query(k-cntL,p<<1|1);
	}
}ST;
struct BIT{
	ll bit[N];
	#define lowbit(x) (x&(-x))
	void init(){
		memset(bit,0,sizeof(bit));
	}
	void add(int p,int v){
		for(;p<=len;p+=lowbit(p))bit[p]+=v;
	}
	ll sum(int p){
		ll res=0;
		for(;p;p-=lowbit(p))res+=bit[p];
		return res;
	}
	ll query(int L,int R){
		return sum(R)-sum(L-1);
	}
}BT;
ll ans;
const ll inf=1LL<<60;
int limL,limR,midd;
void solve(int l,int r){
	int p=ST.query(pos,1);
	int cntL=ST.sum(1,p,1),cntR=ST.sum(p+1,len,1);
	ll res=1LL*tmp[p]*cntL-BT.query(1,p);
	res+=BT.query(p+1,len)-1LL*tmp[p]*cntR;
	if(res<ans){
		ans=res;
		limL=l,limR=r,midd=p;
	}
}
int main(){
	Rd(n),Rd(k);
	pos=k+1>>1;
	for(int i=1;i<=n;i++)Rd(num[i]),tmp[i]=++num[i];
	sort(tmp+1,tmp+1+n);
	len=unique(tmp+1,tmp+1+n)-tmp-1;
	for(int i=1;i<=n;i++)num[i]=lower_bound(tmp+1,tmp+1+len,num[i])-tmp;
	ST.build(1,len,1);
	BT.init();
	for(int i=1;i<=k;i++){
		ST.update(num[i],1,1);
		BT.add(num[i],tmp[num[i]]);
	}
	ans=inf;
	solve(1,k);
	for(int i=k+1;i<=n;i++){
		ST.update(num[i-k],-1,1);
		BT.add(num[i-k],-tmp[num[i-k]]);
		ST.update(num[i],1,1);
		BT.add(num[i],tmp[num[i]]);
		solve(i-k+1,i);
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		if(i<=limR&&i>=limL)printf("%d\n",tmp[midd]-1);
		else printf("%d\n",tmp[num[i]]-1);
	}
	return 0;
}
分享到 评论